#pragma once
#include <vector>
#include <algorithm>
#include <math.h>
#include <fstream>
#include <set>
#include <map>
#include <string>
using namespace std;
#define MINUS_LOG_EPSILON  50

bool split_string(char *str, const char *cut, vector<char *> &strs);
int vector_cmp(const vector<int> & s, const vector<int> & t);


template <class T> inline T _min(T x, T y) { return(x < y) ? x : y; }
template <class T> inline T _max(T x, T y) { return(x > y) ? x : y; }

inline double log_sum_exp(double x,double y)
{
    double vmin = _min(x, y);
    double vmax = _max(x, y);
    if (vmax > vmin + MINUS_LOG_EPSILON) {
      return vmax;
    } else {
      return vmax + log(exp(vmin - vmax) + 1.0);
    }
}


template<class T>
bool is_subset(set<T> &s1, set<T> &s2){//if s1 is empty, return true; else if s2 is empty return false;
	typename set<T>::iterator iter;
	for (iter=s1.begin();iter!=s1.end();++iter){
		if (s2.find(*iter)==s2.end())
			return false;
	}
	return true;
}

template<class T>
bool is_inter(set<T>& s1, set<T>& s2){//if s1 or s2 is empty, return false;
	typename set<T>::iterator iter;
	for (iter=s1.begin();iter!=s1.end();++iter){
		if (s2.find(*iter)!=s2.end())
			return true;
	}
	return false;
}

template<class T>
set<T> set_sub(set<T>& s1, set<T>& s2){//s1-s2
	set<T> r;
	typename set<T>::iterator iter;
	for (iter=s1.begin();iter!=s1.end();++iter){
		if (s2.find(*iter)==s2.end())
			r.insert(*iter);
	}
	return r;
}

template<class T>
set<T> set_union(set<T>& s1, set<T>& s2){//s1-s2
	set<T> r;
	typename set<T>::iterator iter;
	for (iter=s1.begin();iter!=s1.end();++iter)
			r.insert(*iter);
	for (iter=s2.begin();iter!=s2.end();++iter)
			r.insert(*iter);
	return r;
}


template <class T, class cmp_func>
bool vector_search(vector<T> &v, const T & s, int &index, int &insert_pos, cmp_func cmp)
{
	pair<typename vector< T >::const_iterator, typename vector< T >::const_iterator> ip;
	ip = equal_range( v.begin( ), v.end( ), s , cmp);
	index=ip.first-v.begin();
	insert_pos=ip.second-v.begin();
	if ( ip.first == ip.second )//not found
		return false;
	return true;
}



template <class T>
bool vector_search(vector<T> &v, const T & s, int &index, int &insert_pos)
{
	pair<typename vector< T >::const_iterator,typename vector< T >::const_iterator> ip;
	ip = equal_range( v.begin( ), v.end( ), s );
	index=ip.first-v.begin();
	insert_pos=ip.second-v.begin();
	if ( ip.first == ip.second )//not found
	{
		return false;
	}
	return true;
}

template <class T>
bool vector_insert(vector<T> &v, const T & s, int index)
{
	if(index>v.size())return false;
	typename vector<T>::iterator t=v.begin()+index;
	v.insert(t,s);
	return true;
}



template <class T>
int bisearch(T *v, const T & s, int low, int high)
{
	if(high<low)
		return -1;
	int mid=(low+high)/2;
	if(v[mid]==s)
		return mid;
	else if(v[mid]>s)
		return bisearch(v,s,low,mid-1);
	else
		return bisearch(v,s,mid+1,high);
}


template <class T>
int bisearch(T *v, const T & s, int length)//return -1 if not found
{
	return bisearch(v,s,0,length-1);
}

template <class T>
class inverse_cmp
{
	public:
	bool operator()(T s, T t) const 
	{
		return s>t;
	}
};


bool build_table(ifstream &fin, vector<vector<string> > & table, int &lines);



class str_length{
	public:
		size_t operator()(const char *str) const  {return strlen(str)+1;}
};

class str_cmp{
public:
	bool operator()(const char* s, const char* t) const 
	{
		return strcmp(s,t)<0;
	}
};


int ReadMap(std::string fname, std::map<std::string, int> *m) ;
int WriteMap(std::string fname, std::map<std::string, int> *m);
int WriteVecStr(std::string fname,std::vector<std::string>& vec);
int ReadVecStr(std::string fname,std::vector<std::string>& vec);


void SaveBinDouble(const char* file,int num,double* data);
void ReadBinDouble(const char* file,int num,double* data);

void SaveTxtDouble(const char* file,int num,double* data);
void ReadTxtDouble(const char* file,int num,double* data);


void  _assert_loc (const char *expr, const char *filename,unsigned lineno);
#define assert_loc(_Expression) (void)( (!!(_Expression)) || (_assert_loc((#_Expression), (__FILE__), __LINE__), 0) )

FILE* LogFile();


int ArgPos(char *str, int argc, char **argv) ;
double fast_exp(double v);

#define loc_exp(v) exp(v)

template<class T> class memPool
{
public:
	T* _buffer;
	int _buffer_alloc_size;

	memPool() : _buffer(0),_buffer_alloc_size(0) {}
	~memPool() { if(_buffer) free(_buffer);}

	bool alloc(int sz) { 
		if(sz<_buffer_alloc_size) return true; 
		else {
			if(_buffer) free(_buffer);
			_buffer = (T *)malloc(sz * sizeof(T));
			_buffer_alloc_size = sz;
		}
		return _buffer!=0;
	}

	void clear() {
		if(_buffer) free(_buffer);
		_buffer = 0;
		_buffer_alloc_size = 0;
	}

	template<class T> operator T*() { return _buffer;};

};